#include"main.h"

// 要求将所有代码写在本文件内
// 必须实现下列函数。可以自行增加别的函数。
// 请勿修改由老师所提供的main.h文件的内容。

// 初始化名为s的栈，初始化成功，返回0，否则返回1。
int init_stack(Stack *s){
	(*s) = malloc(sizeof (struct stack));
	int *p =(int *) malloc(sizeof((*s)->base) *STACK_MAX_SIZE);
	(*s)->base = p;
	if(!(*s)->base)
		return 1;
	
	(*s)->top = (*s)->base;
	(*s)->number_of_elements = 0;
	return 0;
}
//字符转换为数字
int chTurnInt(char operator){
	switch (operator) {
		case '0':return 0;
		case '1':return 1;
		case '2':return 2;
		case '3':return 3;
		case '4':return 4;
		case '5':return 5;
		case '6':return 6;
		case '7':return 7;
		case '8':return 8;
		case '9':return 9;
	}
	return 0;
}

//操作符判断
bool is_operator(char symbol){
	if(symbol =='+' || symbol == '-' || symbol == '/' || symbol == '*' || symbol == '(' || symbol == ')' || symbol == '#')return 1;
	return 0;
}
//操作数字判断
bool is_operand(char symbol){
	if (symbol<= '9' && symbol >= '1')return 1;
	return 0;
}
// 入栈。返回值表示是否压栈成功：0，成功；1，不成功。
int push(Stack s, char operator_or_operand){
	if(s->top-s->base == STACK_MAX_SIZE){
		return 1;
	}
	if(is_operator(operator_or_operand))
	{
		*(s->top) = operator_or_operand;
	} else if(is_operand(operator_or_operand)){
		//用chTurnInt进行字符与数字的转换，再入栈
		*(s->top) = chTurnInt(operator_or_operand);
	} else{
		
		*(s->top) = operator_or_operand;
		
	}
	s->top++;
	s->number_of_elements++;
	return 0;
};
// 出栈。返回值表示是否出栈成功：0，成功，1，不成功。
int pop(Stack s, char * p_operator_or_operand){
	if(s->top == s->base){
		return 0;
	}
	*p_operator_or_operand = *(--s->top);
	s->number_of_elements--;
	return 1;
}
//返回栈顶元素
int get_top(Stack s, char * symbol){
	if(s->base == s->top){
		return 1;
	}
	*symbol = *(s->top-1) ;
	return 0;
	
}
//判断优先
char compare(char opor_top, char just_opor){
	int i, j;
	char panDuan[][7] = {
		/*运算符之间的优先级制作成一张表格*/
{'>', '>', '<', '<', '<', '>', '>'},
{'>', '>', '<', '<', '<', '>', '>'},
{'>', '>', '>', '>', '<', '>', '>'},
{'>', '>', '>', '>', '<', '>', '>'},
{'<', '<', '<', '<', '<', '=', '0'},
{'>', '>', '>', '>', '0', '>', '>'},
{'<', '<', '<', '<', '<', '0', '='}
	};
	switch (opor_top) {
		case '+': i = 0; break;
		case '-': i = 1; break;
		case '*': i = 2; break;
		case '/': i = 3; break;
		case '(': i = 4; break;
		case ')': i = 5; break;
		case '#': i = 6; break;
	}
	switch (just_opor) {
		case '+':j = 0; break;
		case '-':j = 1; break;
		case '*':j = 2; break;
		case '/':j = 3; break;
		case '(':j = 4; break;
		case ')':j = 5; break;
		case '#':j = 6; break;
	}
	switch (panDuan[i][j]) {
	case '>':
		return 1;
	case '<':
		return -1;
	case '=':
		return 0;
	}
}

int count(int a,int b,char c){
	switch (c) {
		case '+':return a+b;
		case '-':return a-b;
		case '*':return a*b;
		case '/':return a/b;
	}
	return 0;
}

// 用于计算表达式的值，比如#3*(2+6)/4#。
// 返回值表示求值状态：0，合法表达式，成功求值；1，表达式不合法。
// result变量用于返回计算结果。
int evaluate(char * expression, int * result){
	Stack OPND;//存放数字
	Stack OPTR;//存放操作符
	
	char L,R;//存放出栈元素
	
	int left,right;
	
	char symbol;//存放返回的栈顶元素
	char ch;//存放数字和操作符的临时变量
	char oper;
	
	//初始化栈
	init_stack(&OPND);
	init_stack(&OPTR);
	
	//入栈（第一个元素入栈）
	push(OPTR,*expression);
	
	//进行下一个
	ch = *(++expression);
	while (1){
		
		//是否为数字
		if(is_operand(ch)){
			//数字入栈
			push(OPND,ch);
		}
		//是否为操作符
		else if(is_operator(ch)){
			//获取栈顶元素
			get_top(OPTR,&symbol);
			
			switch (compare(symbol,ch)) {
			case 1:
				pop(OPND,&R);		//a先获得出栈元素
				right = (int)R;
				
				pop(OPND,&L);		//b再获得a出栈之后的下一个元素
				left = (int) L;
				
				pop(OPTR,&symbol);//后出栈元素在前（栈先入后出）
				oper =(char) count(left,right,symbol);
				
				push(OPND, oper);//将计算结果再压栈
				get_top(OPTR,&symbol);
				
				expression--;
				break;
			case -1:
				push(OPTR,ch);
				break;
			case 0:
				pop(OPTR,&symbol);
				get_top(OPTR,&symbol);
				break;
			
			}
		} else{
			break;
		}
		ch = *(++expression);
	}
	
	get_top(OPND,&symbol);
	*result =symbol;
	return 1;
}

//测试代码
int main(){
	char *expression = "#3*(2+6)/4#";
	int result;
	evaluate(expression,&result);
		printf("result: %d\n",result);
	
}
